package com.atcumt.Write.sort;

import java.util.Arrays;

/**
 * 插入排序：类似插入扑克牌
 *
 * 从第二个数开始往前比
 * 比它大就往后排
 * 以此类推直到最后一个数
 * 排序前：[4, 5, 6, 3, 2, 1, 10]
 * 第 1 轮插入: [4, 5, 6, 3, 2, 1, 10]
 * 第 2 轮插入: [4, 5, 6, 3, 2, 1, 10]
 * 第 3 轮插入: [3, 4, 5, 6, 2, 1, 10]
 * 第 4 轮插入: [2, 3, 4, 5, 6, 1, 10]
 * 第 5 轮插入: [1, 2, 3, 4, 5, 6, 10]
 * 第 6 轮插入: [1, 2, 3, 4, 5, 6, 10]
 */
public class InsertSort {

    public static void main(String[] args) {

        int[] data = {4, 5, 6, 3, 2, 1, 10};
        System.out.println("排序前：" + Arrays.toString(data));
        insertSort(data);
    }

    /**
     * 插入排序：类似插入扑克牌
     *
     * 从第二个数开始往前比
     * 比它大就往后排
     * 以此类推直到最后一个数
     * 排序前：[4, 5, 6, 3, 2, 1, 10]
     * 第 1 轮插入: [4, 5, 6, 3, 2, 1, 10]
     * 第 2 轮插入: [4, 5, 6, 3, 2, 1, 10]
     * 第 3 轮插入: [3, 4, 5, 6, 2, 1, 10]
     * 第 4 轮插入: [2, 3, 4, 5, 6, 1, 10]
     * 第 5 轮插入: [1, 2, 3, 4, 5, 6, 10]
     * 第 6 轮插入: [1, 2, 3, 4, 5, 6, 10]
     */
    private static int[]  insertSort (int[] arr) {

        int n = arr.length;

        // 从第二个数开始插入！
        for (int i = 1; i < n; i++) {
            int insertVal = arr[i];
            int j = i - 1;

            // 把 i 前面所有大于要插入的牌的牌往后移一位，空出一位给新的牌
            while (j >= 0 && arr[j] > insertVal) {
                arr[j + 1] = arr[j];
                j--;
            }

            arr[j + 1] = insertVal; // 把空出来的一位填满插入的牌

            System.out.println("第 " + i + " 轮插入: " + Arrays.toString(arr));
        }
        return arr;
    }
}
